#include<stdlib.h>
#include<string.h>

/* python code for algo

using recur_backtracking

def generateParenthesis(self, n: int) -> List[str]:
        res = []
        Solve("",0,0,res,n)
        return res

def Solve(state, lcnt, rcnt, res,n):
    if len(state) < 2*n:
        if lcnt > rcnt:
            Solve(state+")",lcnt, rcnt+1, res,n)
        if lcnt < n:
            Solve(state+"(", lcnt+1,rcnt,res,n)
    else:
        res.append(state)
*/

char** generateParenthesis(int n, int* returnSize)
{
    const int NUM = 2000;
    *returnSize = 0;
    char** res = (char**) malloc(sizeof(char*)*NUM);
    char* state = (char*)malloc(sizeof(char)*(2*n+1));state[0] = 0;

    Solve(state,0,0,n,res,returnSize);

    return res;
}
void Solve(char* state, int lcnt, int rcnt, const int n, char** res,int *returnSize)
{
    int NUM = 2*n+1;
    int slen = strlen(state);
    if(slen<2*n)
    {
        if(lcnt>rcnt)
        {
            state[slen] = ')';state[slen+1] = 0;
            Solve(state,lcnt,rcnt+1,n,res,returnSize);
        }
        if(lcnt<n)
        {
            state[slen] = '('; state[slen+1] = 0;
            Solve(state,lcnt+1,rcnt,n,res,returnSize);
        }
    }
    else
    {
        char* tmp = (char*)malloc(sizeof(char)*NUM);
        strcpy(tmp,state);
        res[(*returnSize)++] = tmp;
    }
}